package arithmetic.LeetCode;

import java.util.Arrays;
import java.util.Comparator;
import java.util.PriorityQueue;

/**
 * 给你一个数组events，其中events[i] = [startDayi, endDayi]，表示会议i开始于startDayi，结束于endDayi。
 * 你可以在满足startDayi<= d <= endDayi中的任意一天d参加会议i。注意，一天只能参加一个会议。
 * 请你返回你可以参加的最大会议数目。
 * <p>
 * <p>
 * 示例 1：
 * 输入：events = [[1,2],[2,3],[3,4]]
 * 输出：3
 * 解释：你可以参加所有的三个会议。
 * 安排会议的一种方案如上图。
 * 第 1 天参加第一个会议。
 * 第 2 天参加第二个会议。
 * 第 3 天参加第三个会议。
 * <p>
 * 示例 2：
 * 输入：events= [[1,2],[2,3],[3,4],[1,2]]
 * 输出：4
 * <p>
 * <p>
 * 提示：
 * <p>
 * 1 <= events.length <= 105
 * events[i].length == 2
 * 1 <= startDayi<= endDayi<= 105
 * <p>
 * 链接：https://leetcode.cn/problems/maximum-number-of-events-that-can-be-attended
 *
 * @author jiangfeng on 2023/5/25
 */
public class MaxEvents {
    public static void main(String[] args) {
       // System.out.println(new Solution().maxEvents(new int[][] {{1, 2}, {2, 3}, {3, 4}}));
        System.out.println(new Solution().maxEvents(new int[][] {{1, 2}, {1, 2}, {2, 3}, {3,4},{3, 4}}));
        // 有个问题,到底是按开始时间排序还是结束时间排序?
        System.out.println(new Solution().maxEvents(new int[][] {{1,5}, {1, 5}, {1,5}, {2,3},{2,3}}));
        System.out.println(new Solution().maxEvents(new int[][] {{1,10}, {2, 2}, {2,2}, {2,2},{2,2}}));
        System.out.println(new Solution().maxEvents(new int[][] {{52,79}, {7, 34}}));
    }

    static class Solution {
        public int maxEvents(int[][] events) {
            // 按开始时间升序排个序
            Arrays.sort(events, Comparator.comparingInt((int[] a) -> a[0]));
            PriorityQueue<Integer> q = new PriorityQueue<>(events.length);
            int i = 0, res = 0, cur = 1, size = events.length;
            while (!q.isEmpty() || i < size) {
                // 把开始时间的, 结束时间都放到最小堆里, 上面的都是最小值.结束时间排序.
                while (i < size && events[i][0] == cur) {
                    q.offer(events[i][1]);
                    i++;
                }
                // 结束时间比 当前实际小的就剔除了
                while (!q.isEmpty() && q.peek() < cur) {
                    q.poll();
                }
                // 结束时间比当前实际少或相等的,就加会议
                if (!q.isEmpty() && q.peek() >= cur) {
                    q.poll();
                    res++;
                }
                cur++;


            }
            return res;
        }
    }
}
